Fragmentation of a memory region, such as a heap, can cause many performance issues in computer systems such as long execution times and larger memory requirements. Eliminating, avoiding or diagnosing fragmentation may have significant benefits to the operation of the computer system.
External fragmentation is when the free chunks of memory (“holes”) available for allocation are too small to satisfy a new request to allocate memory, the purpose often being to create a new “object”. In the context of this patent application, an “object” is an entity that has both data and a unique identifier associated with that data; that identifier may be the location of that data in memory. An object is dynamically allocated, that is the area of memory that represents its data can be allocated and freed by an application via an “allocator”. In the context of this patent application, an object is “alive” when an object's data has not been released by the application. The object may be “destroyed” by the application; that is the application deallocates the object's data via the allocator which releases the memory back to the freelist, and the object “dies”. Typically, an allocator needs to traverse a list of holes, known as a freelist, until the allocator can find a hole in the memory that is large enough to satisfy the allocation request. Traversal of the freelist costs execution time and holes that are too small to be allocated waste memory. External fragmentation is often caused when there are objects of different lifetimes allocated within the same area of memory. When short-lived objects die the holes left between the surviving longer-lived objects are often smaller than the new objects that are to be created. The holes collectively are the external fragmentation. The smaller and more extensive the holes are in the freelist, the more fragmented the memory becomes.
The previous disclosures can determine when external fragmentation occurs by analyzing the freelist and recognizing whether the freelist consists of many small holes, but the previous disclosures cannot determine what is causing those holes, where those holes were created, and therefore the previous disclosures cannot offer any suggestions about what computer readable program instructions needs to be changed in order to reduce, avoid or eliminate the fragmentation. It would be desirable to improve the diagnosis and avoidance of fragmentation, specifically external fragmentation.